package chapter01.problem08;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

public class MaxTree {

	/**
	 * 广度优先搜索遍历树
	 * @param head
	 * @return
	 */
	public static String breadthFirst(Node head){
		LinkedList<Node> list = new LinkedList<Node>();
		StringBuilder sb=new StringBuilder(); 
		list.add(head);
		Node node = null;
		Node left=null;
		Node right=null;
		while(!list.isEmpty()){
			node=list.pollFirst();
			sb.append(node.value+" ");
			left = node.left;
			right = node.right;
			if(left!=null)
				list.add(left);
			if(right!=null)
				list.add(right);
		}
		
		return sb.toString();
	}
	
	/**
	 * 得到MaxTree
	 * @param arr
	 * @return
	 */
	public static Node getMaxTree(int[] arr) {
		Stack<Integer> stack = new Stack<Integer>();
		Map<Integer, Integer> leftMap = new HashMap<Integer, Integer>();//保存每一个值左边第一个比它大的数的下标(键是当前值的下标)
		Map<Integer, Integer> rightMap = new HashMap<Integer, Integer>();//保存每一个值右边第一个比它大的数的下标(键是当前值的下标)
		//从左向右遍历，依次找到每个值左边第一个比它大的数的下标
		for (int i = 0; i < arr.length; ++i) {
			if (stack.isEmpty()) {//说明左边没有比它大的数，则保存空值
				stack.push(i);
				leftMap.put(i, null);
			} else {
				while (!stack.isEmpty()) {
					if (arr[stack.peek()] < arr[i]) {//若栈中不空，则与栈顶元素比较，若大于栈顶元素，则弹出栈顶元素并继续迭代，否则退出循环
						stack.pop();
					} else {
						break;
					}
				}
				if (!stack.isEmpty()) {	//如果栈不空的话，栈顶元素就是当前值左边第一个比它大的值的下标，否则说明左边没有比它大的数
					leftMap.put(i, stack.peek());
				} else {
					leftMap.put(i, null);
				}
				stack.push(i);
			}
		}
		stack.clear();
		//从右向左遍历，依次找到每个值右边第一个比它大的数的下标
		for (int i = arr.length - 1; i >= 0; --i) {
			if (stack.isEmpty()) {
				stack.push(i);
				rightMap.put(i, null);
			} else {
				while (!stack.isEmpty()) {
					if (arr[stack.peek()] < arr[i]) {
						stack.pop();
					} else {
						break;
					}
				}
				if (!stack.isEmpty()) {
					rightMap.put(i, stack.peek());
				} else {
					rightMap.put(i, null);
				}
				stack.push(i);
			}
		}
		Map<Integer, Node> map = new HashMap<Integer, Node>();	//保存Node节点，键为数组中的下标，值为arr[i]对应的Node
		for (int i = 0; i < arr.length; ++i) {
			map.put(i, new Node(arr[i]));
		}
		Node head = null;
		int parent;//爹
		for (int i = 0; i < arr.length; ++i) {
			if (leftMap.get(i) == null && rightMap.get(i) == null)
				head = map.get(i);	//如果当前值左右都没有比它大的数则为树根
			else {
				if (leftMap.get(i) == null && rightMap.get(i) != null) {//如果当前值左边没有比它大的数右边有比它大的数则当前值是右边比它大的数的左孩子
					parent = rightMap.get(i);
					map.get(parent).left = map.get(i);
				} else if (leftMap.get(i) != null && rightMap.get(i) == null) {//如果当前值右边没有比它大的数左边有比它大的数则当前值是左边比它大的数的右孩子
					parent = leftMap.get(i);
					map.get(parent).right = map.get(i);
				} else {//如果左右都有比它大的数，选小的当爹。
					if (arr[leftMap.get(i)] < arr[rightMap.get(i)]) {
						parent = leftMap.get(i);
						map.get(parent).right = map.get(i);
					} else {
						parent = rightMap.get(i);
						map.get(parent).left = map.get(i);
					}
				}
			}
		}
		return head;
	}

	public static void main(String[] args) {
		int[] arr = { 3, 4, 5, 1, 2 };
		Node head = MaxTree.getMaxTree(arr);
		String str = breadthFirst(head);
		System.out.println(str);
	}
}
